# -*- coding: utf-8 -*-            
# @Time : 2023/5/19 22:37
# @Author  : lining
# @FileName: 二叉树最大深度.py
"""
自底向上
https://leetcode.cn/problems/maximum-depth-of-binary-tree/
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
我的想法：从根节点开始往下数，一次加1，最后求出最大值
老师的答案：先到达叶子节点，返回0，然后逐级往上加1，一直到根节点,最后返回最大值

"""
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


node5 = TreeNode(7)
node6 = TreeNode(9)
node2 = TreeNode(8, node5, node6)
node8 = TreeNode(13)
node9 = TreeNode(0)
node10 = TreeNode(100)
node7 = TreeNode(11, node10)
node3 = TreeNode(12, node7, node8)
node4 = TreeNode(10, node2, node3)

def find_deep(node):
    if node is None:
        # 层数一定大于等于2层，不用考虑空树或者只有一个根节点的情况
        return 0
    return max(find_deep(node.left), find_deep(node.right))+1

print(find_deep(node4))
